﻿#include <iostream>
#include <stdlib.h>

#define MAX(a, b) (a > b ? a : b)

static int howManyTurnsAtLeast(const int* arr, size_t arrSize)
{
	int total = 0;
	int atLeastNeeded = 0;
	for (int i = 0; i < arrSize; i++)
	{
		total += arr[i];
	}

	if (total % arrSize != 0) return -1;

	int avg = total / arrSize;
	int leftCount = 0;
	for (int i = 0; i < arrSize; i++)
	{
		auto cur = arr[i];
		if (i == 0)
		{
			int targetRight = avg * (arrSize - 1);
			int realRight = total - cur;
			auto needed = abs(targetRight - realRight);
			atLeastNeeded = MAX(atLeastNeeded, needed);
		}
		else if (i == arrSize - 1)
		{
			int targetLeft = avg * (arrSize - 1);
			int realLeft = leftCount;
			auto needed = abs(targetLeft - realLeft);
			atLeastNeeded = MAX(atLeastNeeded, needed);
		}
		else
		{
			int targetLeft = avg * i;
			int realLeft = leftCount;
			int targetRight = avg * (arrSize - i - 1);
			int realRight = total - leftCount - cur;
			int needed = 0;
			if (targetLeft > realLeft && targetRight > realRight)
			{
				needed = abs(targetLeft - realLeft) + abs(targetRight - realRight);
			}
			else
			{
				needed = MAX(abs(targetLeft - realLeft), abs(targetRight - realRight));
			}

			atLeastNeeded = MAX(atLeastNeeded, needed);
		}

		leftCount += cur;
	}

	return atLeastNeeded;
}

// 有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打包机上，
// 放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品
// 进行移动，从而到达物品数量相等才能打包。每个物品重量太大，每次只能搬一个物品进行移动，
// 为了省力，只在相邻的机器上移动。请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。
// 如果不能使每个机器上的物品相同，返回-1。
// 例如[1, 0, 5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后：
// 第一轮: 1 0 <- 5 => 1 1 4
// 第二轮 : 1 <- 1 <- 4 => 2 1 3
// 第三轮 : 2 1 <- 3 => 2 2 2
// 移动了三轮，每个机器上的物品相等，所以返回3
//
//例如[2, 2, 3]表示有3个机器，每个机器上分别有2、2、3个物品，这些物品不管怎么移动，都不能使
// 三个机器上的物品数量相等，返回 - 1.
//
//这个题目是LeetCode上的"洗衣机问题"
// 思路：
// 设第i台机器，左边有x台机器，右边有y台机器。
//
//情况1: i的左边总共需要m个物品，i的右边总共需要n个物品，即i上的物品数量过多
// x  i  y
// -m   -n
// 则i需要贡献出(m+n)个物品，这种情况下，至少需要 (|m|+|n|) 轮操作.
//
//情况2 : i的左边总共需要搬出m个物品，i的右边总共需要搬出n个物品
// x   i   y
// m       n
// 为了平衡每台机器上的物品数量，至少需要max(|m|,|n|)轮操作。
//
//情况3 : i的左边总共需要m个物品，i的右边总共需要搬出n个物品
// x   i   y
// -m       n
// 为了平衡每台机器上的物品数量，至少需要max(|m|,|n|)轮操作。
//
//情况4 : i的左边总共需要搬出m个物品，i的右边总共需要n个物品
// x   i   y
// m      -n
// 为了平衡每台机器上的物品数量，至少需要max(|m|,|n|)轮操作。
//
//对于每个机器的位置都求解需要多少轮，则所有位置中的最大值即为最后的答案。
int main_PackingMachine()
{
	int arr[] = { 1, 1, 2, 4 };
	size_t arrSize = sizeof(arr) / sizeof(int);
	int atLeast = howManyTurnsAtLeast(arr, arrSize);
	printf("%d\n", atLeast);
	return 0;
}